package c_leetcode.a_62_unique_paths;

import java.util.Arrays;

/**
 * 不同路径
 * 时间复杂度    O(m*n)
 * 空间复杂度    O(m*n)
 * ------
 * 思路：1.每个网格单元路径 = 左单元格路径 + 右单元格路径
 * 2.初始位置单元格路径 = 1
 * 3.第一行单元格路径  = 1
 * 4.第一列单元格路径  = 1
 *
 * @author He Kuntao
 * @since 2025/3/11 13:24
 */
public class UniquePaths {
    public static void main(String[] args) {
        System.out.println(new UniquePaths().uniquePaths(3, 7));
    }

    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int[] temp : dp) {
            Arrays.fill(temp, 1);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}
